package com.cat.dynamicPlanning;

import java.util.HashSet;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/extra-characters-in-a-string/
 * @create 2025/9/5 14:41
 * @since JDK17
 */

public class Solution75 {
    public int minExtraChar(String s, String[] dictionary) {
        int n = s.length(), m = dictionary.length;
        int[] dp = new int[n + 1];
        HashSet<String> set = new HashSet<String>();
        for (int i = 0; i <= n; i++) {
            dp[i] = i;
        }

        for (int i = 0; i < m; i++) {
            set.add(dictionary[i]);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (set.contains(s.substring(j, i))) {
                    dp[i] = Math.min(dp[i], dp[j]); // 匹配成功
                }
            }
            dp[i] = Math.min(dp[i - 1] + 1, dp[i]);
        }
        return dp[n];
    }
}
